/**
 * @file prs_qsort.cpp
 * @author ultralyj (1951578@tongji.edu.cn)
 * @brief 并行排序算法的若干实现
 * @version 0.1
 * @date 2021-12-15
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#include "prs_qsort.h"

static int64_t prs_partition(float_t* sortData, int64_t indexBegin, int64_t indexEnd);
static void prs_qsort_paraTask(float_t* sortData, int64_t indexBegin, int64_t indexEnd, size_t threadSplit);

/**
 * @brief 快速排序的串行实现
 * 
 * @param sortData 
 * @param indexBegin 
 * @param indexEnd 
 */
void prs_qsort(float_t* sortData, int64_t indexBegin, int64_t indexEnd)
{
	if (indexBegin < indexEnd)
	{
		int64_t split = prs_partition(sortData, indexBegin, indexEnd);
		{
			prs_qsort(sortData, indexBegin, split - 1);
			prs_qsort(sortData, split + 1, indexEnd);
		}
	}
}

/**
 * @brief 
 * 
 * @param sortData 
 * @param indexBegin 
 * @param indexEnd 
 * @param numThreads 
 */
void prs_qsort_omp(float_t* sortData, int64_t indexBegin, int64_t indexEnd, size_t numThreads)
{
    size_t threadSplit = 2000;
#pragma omp parallel num_threads((int)numThreads) 
    {
#pragma omp single 
        {
            prs_qsort_paraTask(sortData, indexBegin, indexEnd, threadSplit);
        }
    }
}

/**
 * @brief 
 * 
 * @param sortData 
 * @param indexBegin 
 * @param indexEnd 
 * @return int64_t 
 */
static int64_t prs_partition(float_t* sortData, int64_t indexBegin, int64_t indexEnd)
{
	float_t midData = sortData[indexBegin];
	while (indexBegin < indexEnd)
	{
		while (indexBegin < indexEnd && sortData[indexEnd] >= midData)
		{
			indexEnd--;
		}
		sortData[indexBegin] = sortData[indexEnd];
		while (indexBegin < indexEnd && sortData[indexBegin] <= midData)
		{
			indexBegin++;
		}
		sortData[indexEnd] = sortData[indexBegin];
	}
	sortData[indexBegin] = midData;
	/* 返回中轴的位置，再进行分离 */
	return indexBegin;
}

/**
 * @brief 
 * 
 * @param sortData 
 * @param indexBegin 
 * @param indexEnd 
 * @param threadSplit 
 */
static void prs_qsort_paraTask(float_t* sortData, int64_t indexBegin, int64_t indexEnd, size_t threadSplit)
{
    int64_t i = indexBegin, j = indexEnd;
    float_t tmp;
    float_t pivot = sortData[(indexBegin + indexEnd) / 2];
    //进行数组分割，分成两部分（符合左小右大）
    while (i <= j)
    {
        while (sortData[i] < pivot)
            i++;
        while (sortData[j] > pivot)
            j--;
        if (i <= j) 
        {
            tmp = sortData[i];
            sortData[i] = sortData[j];
            sortData[j] = tmp;
            i++;
            j--;
        }
    }
    if (indexEnd - indexBegin< (int64_t)threadSplit)
	{
        if (indexBegin < j)
		{
            prs_qsort_paraTask(sortData, indexBegin, j, threadSplit);
        }
        if (i < indexEnd)
		{
            prs_qsort_paraTask(sortData, i, indexEnd, threadSplit);
        }
    }
    else
	{
        #pragma omp parallel default(none) shared(sortData,threadSplit)
        {
            #pragma omp parallel sections 
            {
                #pragma omp section
                {
                    prs_qsort_paraTask(sortData, indexBegin, j, threadSplit);
                }
                #pragma omp section
                {
                    prs_qsort_paraTask(sortData, i, indexEnd, threadSplit);
                }
            }   
        }    
    }
}


void qrs_qsort_merge(float_t* sortData, int64_t indexBegin, int64_t indexMin, int64_t indexEnd)
{                          //需要传入新的开辟空间tmp用来存放排序的元素
    int64_t i_start = indexBegin;   //对应上图的is
    int64_t i_end = indexMin;       //对应上图的ie
    int64_t j_start = indexMin + 1; //对应上图的js
    int64_t j_end = indexEnd;       //对应上图的je
    int64_t k = 0;           //访问临时空间的索引变量

    float_t* temp = new float_t[indexEnd - indexBegin + 1];
    //合并两个有序序列
    while (i_start <= i_end && j_start <= j_end)
    {
        if (sortData[i_start] > sortData[j_start]) //将较小的数优先放入临时空间
        {
            temp[k] = sortData[j_start];
            j_start++;
            k++;
        }
        else
        {
            temp[k] = sortData[i_start];
            i_start++;
            k++;
        }
    }
    //检测两个有序序列合并后是否还有剩余元素
    while (i_start <= i_end)
    {
        temp[k] = sortData[i_start];
        i_start++;
        k++;
    }
    while (j_start <= j_end)
    {
        temp[k] = sortData[j_start];
        j_start++;
        k++;
    }
    //辅助空间数据覆盖原空间
    for (int64_t i = 0; i < k; i++)
    {
        sortData[indexBegin + i] = temp[i];
    }
    delete temp;
}
